# source:https://leetcode.cn/problems/count-good-numbers/?envType=daily-question&envId=2025-04-13 快速幂
from typing import List


class Solution:
    def __init__(self):
        self.MOD = 1_000_000_000 + 7
    def count(self, base, v):
        if v == 0:
            return 1
        if v % 2 == 0:
            return self.count(base, v//2)**2 % self.MOD
        else:
            return base * self.count(base, v-1) % self.MOD
        
    def countGoodNumbers(self, n: int) -> int:
        if n%2 == 0:
            res = self.count(5, n//2) * self.count(4, n//2) % self.MOD
        else:
            res = self.count(5, n//2+1) * self.count(4, n//2) % self.MOD
        return res % self.MOD

# source:https://leetcode.cn/problems/count-good-triplets/?envType=daily-question&envId=2025-04-14 hash-table
class Solution:
    def countGoodTriplets(self, arr: List[int], a: int, b: int, c: int) -> int:
        store = [[[],[]] for _ in range(len(arr)-2)]
        for j in range(1, len(arr)-1):
            base = arr[j]
            for i in range(j):
                if abs(base - arr[i]) <= a:
                    store[j-1][0].append(arr[i])
            for k in range(j+1, len(arr)):
                if abs(base - arr[k]) <= b:
                    store[j-1][1].append(arr[k])
        # print(store)   
        ans = 0
        for i in range(len(store)):
            left = store[i][0]
            right = store[i][1]
            for l in left:
                for r in right:
                    if abs(l-r) <= c:
                        ans += 1
        return ans
